#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
    int sum(int end, vector<int>& a)
    {
        int count = 0;
        for (int n = 0; n <= end; n++)
        {
            count += a[n];
        }
        return count;
    }
    vector<int> runningSum(vector<int>& nums) {
        int arr[1000];
        for (int i = 0; i < nums.size(); i++)
        {
            arr[i] = sum(i, nums);
        }
        return vector<int>(arr, arr + nums.size());
    }
};
class Solution1 {
public:
    int searchInsert(vector<int>& nums, int target) {
        int mid;
        int left = 0, right = nums.size() - 1;
        if (target > nums[right])
        {
            return right + 1;
        }
        else if (target < nums[left])
        {
            return left;
        }
        while (left <= right)
        {
            mid = left + (right - left) / 2;
            if (target > nums[mid])
            {
                left = mid + 1;
            }
            else if (target < nums[mid])
            {
                right = mid - 1;
            }
            else
            {
                return mid;
            }
        }
        return left;
    }
};
int main()
{
	vector<int> a;
	a.push_back(1);
	a.push_back(2);
	a.push_back(3);
	a.push_back(4);
	//for (auto e : arr)
	//{
	//	cout << e;
	//}
	//for (int i = 0; i < arr.size(); i++)
	//{
	//	cout << arr[i] << " ";
	//}
    //Solution s;
    //s.runningSum(a);
    Solution1 s1;
    vector<int> v{ 1,3 };
    cout<<s1.searchInsert(v, 2);
	return 0;
}
